package com.singzi.leetcode.N600;

import com.singzi.leetcode.obj.TreeNode;

import java.util.*;

public class T0508 {
}

class Solution0508 {
    TreeSet<int[]> set;
    TreeMap<Integer, Integer>map;
    public int[] findFrequentTreeSum(TreeNode root) {
        map = new TreeMap<>();
        set = new TreeSet<>((o1, o2) -> o1[0] == o2[0]?o2[1] - o1[1]:o2[0] - o1[0]);
        postOrder(root);
        List<Integer> ans = new ArrayList<>();
        Iterator<int[]> iterator = set.iterator();
        int target = set.first()[0];
        while(iterator.hasNext()){
            int []nums = iterator.next();
            if(nums[0] != target)
                break;
            ans.add(nums[1]);
        }
        int []res = new int[ans.size()];
        for(int i = 0;i < ans.size();i++){
            res[i] = ans.get(i);
        }
        return res;

    }

    private int  postOrder(TreeNode root) {
        int left = 0, right = 0;
        int[] nums = new int[2];
        if(root.left != null) left += postOrder(root.left);
        if(root.right != null) left += postOrder(root.right);
        root.val =  root.val + left + right;
        if(map.containsKey(root.val)){
            nums[1] = root.val;
            nums[0] = map.get(nums[1]);
            map.put(nums[1], nums[0] + 1);
            set.remove(nums);
            nums[0]++;
            set.add(nums);
        }else {
            map.put(root.val, 1);
            set.add(new int[]{1, root.val});
        }
        return  root.val;
    }
}